package part2;

/**
 * @Author: shaochong
 * @Date: 2021/8/15
 * @Description:给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 动态规划:
 *
 * 用 f(i) 代表以第 ii 个数结尾的「连续子数组的最大和」,
 * f(i)=max{f(i−1)+nums[i],nums[i]}
 *
 * 易错点:
 * * 动态规划的3个关键点（1）状态转移方程 （2）初始结果值 （3）记录最优解
 */
public class Solution53 {
    public static int maxSubArray(int[] nums) {
        int[] maxi = new int[nums.length];
        // 初始值
        int max = nums[0];
        for (int i = 0; i<nums.length; i++) {
            //  用 f(i) 代表以第 ii 个数结尾的「连续子数组的最大和」, f(i)=max{f(i−1)+nums[i],nums[i]}
            maxi[i] = i == 0 ? nums[i] : Math.max(maxi[i-1] + nums[i], nums[i]);
            // 判断当前是否为最优解
            if (maxi[i] > max) {
                max = maxi[i];
            }
        }
        return max;
    }


    /**
     * 优化dp,不存在全部的fi
     * @param nums
     * @return
     */
    public static int maxSubArray2(int[] nums) {
        int max = nums[0];
        int pre = nums[0];
        for (int i = 0; i<nums.length; i++) {
            if (pre + nums[i] > nums[i]) {
                pre = pre + nums[i];
            }
            // 当前最优解
            if (pre > max) {
                max = pre;
            }
        }
        return max;
    }




    public static void main(String[] args) {

    }
}
